package structure.heap.test;

import structure.heap.basic.MyBinaryHeap;
import utility.printer.BinaryTrees;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 项目名称: god
 * 包 名 称: structure.heap.test
 * 类 名 称: Main
 * 类 描 述: TODO
 * 创建时间: 2020/6/18 3:25 下午
 * 创 建 人: Justice
 */
public class Main {
    public static void main(String[] args) {
        test4();
    }

    private static void test() {
        // src：要复制的数组(源数组)
        // srcPos：复制源数组的起始位置
        // dest：目标数组
        // destPos：目标数组的下标位置
        // length：要复制的长度
        int[] array = {1, 2, 3, 4, 9, 10};
        int[] array1 = new int[100];
        System.arraycopy(array, 0, array1, 0, array.length);
        System.out.println(Arrays.toString(array1));
    }

    private static void test2() {
        MyBinaryHeap<Integer> binaryHeap = new MyBinaryHeap<>();
        binaryHeap.add(68);
        binaryHeap.add(72);
        binaryHeap.add(43);
        binaryHeap.add(50);
        binaryHeap.add(38);
        binaryHeap.add(10);
        binaryHeap.add(90);
        binaryHeap.add(65);
        binaryHeap.add(33);
        binaryHeap.add(12);
        BinaryTrees.println(binaryHeap);
        System.out.println("*****************************");
        // binaryHeap.remove();
        binaryHeap.replace(1000);
        BinaryTrees.println(binaryHeap);
    }

    private static void test3() {
        Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
        // 构建小顶堆
        MyBinaryHeap<Integer> binaryHeap = new MyBinaryHeap<>(data, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        BinaryTrees.println(binaryHeap);
    }

    private static void test4() {
        // top K 问题：找出最大的前k个数
        // 构建小顶堆
        MyBinaryHeap<Integer> heap = new MyBinaryHeap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int k = 3;
        Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93,
                91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
                90, 6, 65, 49, 3, 26, 61, 21, 48};
        for (Integer datum : data) {
            if (heap.size() < k) {
                // 前k个数添加到小顶堆
                heap.add(datum); // log(k)
            } else if (datum > heap.get()) { // 如果是第k + 1个数，并且大于堆顶元素
                heap.replace(datum); // log(k)
            }
        }
        BinaryTrees.println(heap);
    }
}
